{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #One Edit Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isOneEditDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相隔为 1 的编辑距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串 <code>s</code> 和&nbsp;<code>t</code> ，如果它们的编辑距离为 <code>1</code> ，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>字符串 <code>s</code> 和字符串 <code>t</code> 之间满足编辑距离等于 1 有三种可能的情形：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>往 <code>s</code>&nbsp;中插入 <strong>恰好一个</strong> 字符得到 <code>t</code></li>\n",
    "\t<li>从 <code>s</code>&nbsp;中删除 <strong>恰好一个</strong> 字符得到 <code>t</code></li>\n",
    "\t<li>在 <code>s</code>&nbsp;中用 <strong>一个不同的字符</strong> 替换 <strong>恰好一个</strong> 字符得到 <code>t</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><strong><em>s</em></strong> = \"ab\", <strong><em>t</em></strong> = \"acb\"\n",
    "<strong>输出: </strong>true\n",
    "<strong>解释: </strong>可以将 'c' 插入字符串 <strong><em>s</em></strong>&nbsp;来得到 <em><strong>t</strong></em>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><strong><em>s</em></strong> = \"cab\", <strong><em>t</em></strong> = \"ad\"\n",
    "<strong>输出: </strong>false\n",
    "<strong>解释: </strong>无法通过 1 步操作使 <em><strong>s</strong></em> 变为 <em><strong>t</strong></em>。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length, t.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 和&nbsp;<code>t</code>&nbsp;由小写字母，大写字母和数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [one-edit-distance](https://leetcode.cn/problems/one-edit-distance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [one-edit-distance](https://leetcode.cn/problems/one-edit-distance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ab\"\\n\"acb\"', '\"\"\\n\"\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        '''\n",
    "        最大编辑距离只需要判断到1就可以了，不需要dp，贪心即可\n",
    "        '''\n",
    "        if s == t:\n",
    "            return False\n",
    "        m, n = len(s), len(t)\n",
    "        if abs(m - n) > 1:\n",
    "            return False\n",
    "\n",
    "        i = 0\n",
    "        while i < m and i < n and s[i] == t[i]:\n",
    "            i += 1\n",
    "\n",
    "        return s[i + 1:] == t[i + 1:] or \\\n",
    "            s[i + 1:] == t[i:] or \\\n",
    "            s[i:] == t[i + 1:]\n",
    "\n",
    "        '''\n",
    "        if m == 0:\n",
    "            return n == 1\n",
    "        if n == 0:\n",
    "            return m == 1\n",
    "        result = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            result[i + 1][0] = i + 1\n",
    "        for j in range(n):\n",
    "            result[0][j + 1] = j + 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    result[i + 1][j + 1] = result[i][j]\n",
    "                else:\n",
    "                    result[i + 1][j + 1] = min(result[i][j],result[i + 1][j], result[i][j + 1]) + 1\n",
    "        return result[m][n] == 1\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: 'str', t: 'str') -> 'bool':\n",
    "        ns,nt=len(s),len(t)\n",
    "        if ns>nt:\n",
    "            return self.isOneEditDistance(t, s)\n",
    "        if nt-ns>1: return False\n",
    "        for i in range(ns):\n",
    "            if s[i]!=t[i]:\n",
    "                if ns==nt:\n",
    "                    return s[i+1:]==t[i+1:]\n",
    "                else:\n",
    "                    return s[i:]==t[i+1:]\n",
    "        return ns+1==nt\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #    ns, nt = len(s), len(t)\n",
    "\n",
    "    #    # 确保 s 比 t 短。\n",
    "    #    if ns > nt:\n",
    "    #        return self.isOneEditDistance(t, s) #### 交换位置\n",
    "    #    # 如果长度差异大于 1，则字符串不是一个编辑距离。\n",
    "    #    if nt - ns > 1:\n",
    "    #        return False\n",
    "\n",
    "    #    for i in range(ns):\n",
    "    #        if s[i] != t[i]:\n",
    "    #            # 如果字符串具有相同的长度\n",
    "    #            if ns == nt:\n",
    "    #                return s[i + 1:] == t[i + 1:]\n",
    "    #            # 如果字符串具有不同的长度\n",
    "    #            else:\n",
    "    #                return s[i:] == t[i + 1:]\n",
    "       \n",
    "    #    # 如果在 ns 距离上没有差异，则仅当 t 有多一个字符时，字符串才有一次编辑。\n",
    "    #    return ns + 1 == nt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        ls = len(s)\n",
    "        lt = len(t)\n",
    "        res = ls - lt\n",
    "        check = 0\n",
    "        if res == 1:\n",
    "            if t in s:\n",
    "                return True\n",
    "            else:\n",
    "                for i in range(0, ls):\n",
    "                    if t[i] != s[i]:\n",
    "                        check += 1\n",
    "                        t = t[0 : i] + s[i] + t[i : ]\n",
    "        elif res == -1:\n",
    "            if s in t:\n",
    "                return True\n",
    "            else:\n",
    "                for i in range(0, lt):\n",
    "                    if s[i] != t[i]:\n",
    "                        check += 1\n",
    "                        s = s[0 : i] + t[i] + s[i : ]\n",
    "        elif res == 0:\n",
    "            for i in range(0, lt):\n",
    "                if s[i] != t[i]:\n",
    "                    check += 1\n",
    "        else:\n",
    "            return False\n",
    "        if check != 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        #可以双指针枚举判断\n",
    "        a,b=len(s),len(t)\n",
    "        if abs(a-b)>1:\n",
    "            return False\n",
    "        if a>b:\n",
    "            i,j=0,0\n",
    "            flag=False\n",
    "            while i<a and j<b:\n",
    "                if s[i]==t[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                    continue\n",
    "                if not flag:\n",
    "                    flag=True\n",
    "                    i+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j+=1\n",
    "            return True\n",
    "        elif a<b:\n",
    "            i,j=0,0\n",
    "            flag=False\n",
    "            while i<a and j<b:\n",
    "                if s[i]==t[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                    continue\n",
    "                if not flag:\n",
    "                    flag=True\n",
    "                    j+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j+=1\n",
    "            return True\n",
    "        else:\n",
    "            i,j=0,0\n",
    "            flag=False\n",
    "            while i<a and j<b:\n",
    "                if s[i]==t[j]: \n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                    continue\n",
    "                if not flag:\n",
    "                    flag=True\n",
    "                else:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j+=1\n",
    "            return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        if s == t:\n",
    "            return False\n",
    "        if len(s) > len(t):\n",
    "            return self.isOneEditDistance(t, s)\n",
    "        if len(s) < len(t)-1:\n",
    "            return False\n",
    "        eq_length = len(s) == len(t)\n",
    "        one_edit = False\n",
    "        i, j = 0, 0\n",
    "        while i < len(s) and j < len(t):\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                if one_edit:\n",
    "                    return False\n",
    "                if eq_length:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "                one_edit = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        if abs(len(s) - len(t)) > 1:\n",
    "            return False\n",
    "        if len(s) > len(t):\n",
    "            return self.isOneEditDistance(t,s)\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            if s[i] != t[i]:\n",
    "                if len(s) == len(t):\n",
    "                    return s[i+1:] == t[i+1:]\n",
    "                else:\n",
    "                    return s[i:] == t[i+1:]\n",
    "        \n",
    "        return len(s)+1 == len(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        m, n = len(s), len(t)\n",
    "        cnt = 0\n",
    "        if m < n:\n",
    "            if n - m != 1: return False\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] == t[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    cnt += 1\n",
    "                    j += 1\n",
    "                if cnt > 2: return False\n",
    "            return cnt == 1 or n - j == 1\n",
    "        \n",
    "        elif m > n:\n",
    "            if m - n != 1: return False\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] == t[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    cnt += 1\n",
    "                    i += 1\n",
    "                if cnt > 2: return False\n",
    "            return cnt == 1 or m - i == 1\n",
    "        \n",
    "        else:\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] == t[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    cnt += 1\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                if cnt > 2: return False\n",
    "            return cnt == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        a = 0\n",
    "        b = 0\n",
    "        lis_s = list(s) + ['+']\n",
    "        lis_t = list(t) + ['+']\n",
    "        mark_change = 0\n",
    "        cache_a = 0\n",
    "        cache_b = 0\n",
    "        if s == t:\n",
    "            return False\n",
    "\n",
    "        # while not (lis_s[a] == '' and lis_t[b] == ''):\n",
    "        while True:\n",
    "            if a == len(lis_s) and b == len(lis_t):\n",
    "                return True\n",
    "            if a == len(lis_s) or b == len(lis_t):\n",
    "                a = cache_a\n",
    "                b = cache_b\n",
    "            if lis_s[a] != lis_t[b]:\n",
    "                if mark_change == 3:\n",
    "                    return False\n",
    "                else:\n",
    "                    if mark_change == 0:\n",
    "                        cache_a = a\n",
    "                        cache_b = b\n",
    "                        mark_change += 1\n",
    "                        a += 1\n",
    "                    elif mark_change == 1:\n",
    "                        a = cache_a\n",
    "                        b = cache_b\n",
    "                        b += 1\n",
    "                        mark_change += 1\n",
    "                    else:\n",
    "                        a = cache_a\n",
    "                        b = cache_b\n",
    "                        a += 1\n",
    "                        b += 1\n",
    "                        mark_change += 1\n",
    "                # if a == len(lis_s) or b == len(lis_t):\n",
    "                #     mark_change += 1\n",
    "            else:\n",
    "                a += 1\n",
    "                b += 1\n",
    "                # mark_change == 0\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        if s == t:\n",
    "            return False\n",
    "        ls= len(s)\n",
    "        lt = len(t)\n",
    "        if ls == lt or (ls +1 == lt or lt + 1== ls):\n",
    "            if ls== lt : \n",
    "                return self.check_if_equal( s, t) \n",
    "            if lt > ls:\n",
    "                return self.check_if_g1( s, t)\n",
    "            else:\n",
    "                return self.check_if_g1( t, s)\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def check_if_equal(self, s, t):\n",
    "        cnt = 0 \n",
    "        for a, b in zip(s,t):\n",
    "            if a != b :\n",
    "                cnt += 1\n",
    "                if cnt > 1:\n",
    "                    return False \n",
    "            print(a,b, cnt)\n",
    "        return True\n",
    "\n",
    "    def check_if_g1(self, s,l):\n",
    "        m, n = len(s), len(l)\n",
    "        i ,j = 0, 0\n",
    "        print(s,l)\n",
    "        while i < m and j < n:\n",
    "            if s[i] == l[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "            if j - i >= 2:\n",
    "                return False\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        if abs(len(s)-len(t))>=2:\n",
    "            return False\n",
    "\n",
    "        if len(s)>len(t):\n",
    "            t,s = s[:], t[:]\n",
    "\n",
    "        if s == \"\" and len(t)>2: return False\n",
    "        if s ==\"\" and len(t) == 1: return True\n",
    "                \n",
    "\n",
    "        if s == t:\n",
    "            return False\n",
    "\n",
    "        if len(s)==len(t):\n",
    "            cnt = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] != t[i]:\n",
    "                    cnt += 1\n",
    "                if cnt > 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        cnt = 0\n",
    "        idx = 0\n",
    "        print(s,t)\n",
    "        while idx+1:\n",
    "            print(idx, cnt)\n",
    "            if idx+cnt>len(t)-1 or idx>=len(s):\n",
    "                return True\n",
    "\n",
    "            if s[idx] != t[idx+cnt]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                idx += 1\n",
    "\n",
    "            if cnt >= 2:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        self.cache = dict()\n",
    "        return self.isOneEditDistanceRecursive(s, len(s), t, len(t), 1)\n",
    "\n",
    "    def isOneEditDistanceRecursive(self, s, i, t, j, editCount):\n",
    "        if editCount < 0:\n",
    "            return False\n",
    "        if editCount == 0:\n",
    "            return s[:i] == t[:j]\n",
    "        if i == 0:\n",
    "            return j == editCount\n",
    "        if j == 0:\n",
    "            return i == editCount\n",
    "        \n",
    "        key = (i, j, editCount)\n",
    "        if key in self.cache:\n",
    "            return self.cache[key]\n",
    "\n",
    "        if s[i-1] != t[j-1]:\n",
    "            # insert\n",
    "            if self.isOneEditDistanceRecursive(s, i, t, j-1, editCount-1):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "            # delete\n",
    "            if self.isOneEditDistanceRecursive(s, i-1, t, j, editCount-1):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "            # replace\n",
    "            if self.isOneEditDistanceRecursive(s, i-1, t, j-1, editCount-1):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "        else:\n",
    "            if self.isOneEditDistanceRecursive(s, i-1, t, j-1, editCount):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "\n",
    "        self.cache[key] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        self.cache = dict()\n",
    "        return self.isOneEditDistanceRecursive(s, len(s), t, len(t), 1)\n",
    "\n",
    "    def isOneEditDistanceRecursive(self, s, i, t, j, editCount):\n",
    "        if i == 0:\n",
    "            return j == editCount\n",
    "        if j == 0:\n",
    "            return i == editCount\n",
    "        \n",
    "        key = (i, j, editCount)\n",
    "        if key in self.cache:\n",
    "            return self.cache[key]\n",
    "\n",
    "        if editCount == 0:\n",
    "            self.cache[key] = s[:i] == t[:j]\n",
    "            return self.cache[key]\n",
    "\n",
    "        if s[i-1] != t[j-1]:\n",
    "            # insert\n",
    "            if self.isOneEditDistanceRecursive(s, i, t, j-1, editCount-1):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "            # delete\n",
    "            if self.isOneEditDistanceRecursive(s, i-1, t, j, editCount-1):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "            # replace\n",
    "            if self.isOneEditDistanceRecursive(s, i-1, t, j-1, editCount-1):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "        else:\n",
    "            if self.isOneEditDistanceRecursive(s, i-1, t, j-1, editCount):\n",
    "                self.cache[key] = True\n",
    "                return True\n",
    "\n",
    "        self.cache[key] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        m, n = len(s), len(t)\n",
    "        def dfs(i, j, mem, flag):\n",
    "            if (i, j) in mem:\n",
    "                return mem[(i, j)]\n",
    "            ans = 0\n",
    "            if i == m and j == n:\n",
    "                ans = 0\n",
    "            elif i == m:\n",
    "                ans = n - j\n",
    "            elif j == n:\n",
    "                ans = m - i\n",
    "            else:\n",
    "                if s[i] == t[j]:\n",
    "                    ans = dfs(i + 1, j + 1, mem, flag)\n",
    "                else:\n",
    "                    if not flag:\n",
    "                        ans = 2\n",
    "                    else:\n",
    "                        ans = 1 + min(dfs(i + 1, j, mem, False), dfs(i, j + 1, mem, False), dfs(i + 1, j + 1, mem, False)) \n",
    "            mem[(i, j)] = ans\n",
    "            return ans\n",
    "        return dfs(0, 0, {}, True) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        m, n = len(s), len(t)\n",
    "        def dfs(i, j, mem, flag):\n",
    "            if (i, j) in mem:\n",
    "                return mem[(i, j)]\n",
    "            ans = 0\n",
    "            if i == m and j == n:\n",
    "                ans = 0\n",
    "            elif i == m:\n",
    "                ans = n - j\n",
    "            elif j == n:\n",
    "                ans = m - i\n",
    "            else:\n",
    "                if s[i] == t[j]:\n",
    "                    ans = dfs(i + 1, j + 1, mem, flag)\n",
    "                else:\n",
    "                    if not flag:\n",
    "                        ans = 2\n",
    "                    else:\n",
    "                        ans = 1 + min(dfs(i + 1, j, mem, False), dfs(i, j + 1, mem, False), dfs(i + 1, j + 1, mem, False)) \n",
    "            mem[(i, j)] = ans\n",
    "            return ans\n",
    "        return dfs(0, 0, {}, True) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self, s, t, i, j, rem):\n",
    "        if i == len(s) and j == len(t):\n",
    "            if rem == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        if rem < 0: return False\n",
    "        rets = []\n",
    "        if j < len(t):\n",
    "            rets.append(self.dp(s,t,i,j+1,rem-1)) #insert\n",
    "        if i < len(s):\n",
    "            rets.append(self.dp(s,t,i+1,j,rem-1)) #delete\n",
    "        if i < len(s) and j < len(t) and s[i]==t[j]:\n",
    "            rets.append(self.dp(s,t,i+1,j+1,rem)) #equal\n",
    "        if i < len(s) and j < len(t) and s[i]!=t[j]:\n",
    "            rets.append(self.dp(s,t,i+1,j+1,rem-1)) #subs\n",
    "        if any(rets):\n",
    "            return True\n",
    "        return False\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        return self.dp(s,t,0,0,1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        def f(a, b, c):\n",
    "            if a < 0 or b < 0:\n",
    "                if c+abs(a-b)==1:\n",
    "                    return True\n",
    "                return False\n",
    "            if s[a] == t[b]:\n",
    "                return f(a-1, b-1, c)\n",
    "            else:\n",
    "                if c == 1:\n",
    "                    return False\n",
    "                else:\n",
    "                    return f(a - 1, b, c + 1) or f(a, b - 1, c + 1) or f(a - 1, b - 1, c + 1)\n",
    "\n",
    "        return f(len(s)-1, len(t)-1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "\n",
    "        if s==t or abs(len(s)-len(t))>1: return False\n",
    "\n",
    "        def dp(i,j,flag):\n",
    "            if i==j==-1: return True\n",
    "            if (i==-1 and j==0 or j==-1 and i==0) and flag==1: return True\n",
    "            # elif i==-1 or j==-1: return False\n",
    "            if s[i]==t[j]: return dp(i-1,j-1,flag)\n",
    "            if i>j: \n",
    "                if flag==1: return dp(i-1,j,0)\n",
    "                else: return False\n",
    "            elif i<j: \n",
    "                if flag==1: return dp(i,j-1,0)\n",
    "                else: return False\n",
    "            else: \n",
    "                if flag==1: return dp(i-1,j-1,0)\n",
    "                else: return False\n",
    "\n",
    "        return dp(len(s)-1,len(t)-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "\n",
    "        if s==t or abs(len(s)-len(t))>1: return False\n",
    "\n",
    "        def dp(i,j,flag):\n",
    "            if i==j==-1: return True\n",
    "            if (i==-1 and j==0 or j==-1 and i==0) and flag==1: return True\n",
    "            # elif i==-1 or j==-1: return False\n",
    "            if s[i]==t[j]: return dp(i-1,j-1,flag)\n",
    "            if i>j: \n",
    "                if flag==1: return dp(i-1,j,0)\n",
    "                else: return False\n",
    "            elif i<j: \n",
    "                if flag==1: return dp(i,j-1,0)\n",
    "                else: return False\n",
    "            else: \n",
    "                if flag==1: return dp(i-1,j-1,0)\n",
    "                else: return False\n",
    "\n",
    "        return dp(len(s)-1,len(t)-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "\n",
    "        if s==t: return False\n",
    "\n",
    "        def dp(i,j,flag):\n",
    "            if i==j==-1: return True\n",
    "            if (i==-1 and j==0 or j==-1 and i==0) and flag==1: return True\n",
    "            elif i==-1 or j==-1: return False\n",
    "            if s[i]==t[j]: return dp(i-1,j-1,flag)\n",
    "            if i>j: \n",
    "                if flag==1: return dp(i-1,j,0)\n",
    "                else: return False\n",
    "            elif i<j: \n",
    "                if flag==1: return dp(i,j-1,0)\n",
    "                else: return False\n",
    "            else: \n",
    "                if flag==1: return dp(i-1,j-1,0)\n",
    "                else: return False\n",
    "\n",
    "        return dp(len(s)-1,len(t)-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "        if s==t:\n",
    "            return False\n",
    "        \n",
    "        # if len(s)>len(t):\n",
    "        #     return self.isOneEditDistance(t,s)\n",
    "        len1=len(s)\n",
    "        len2=len(t)\n",
    "        if abs(len2-len1)>1:\n",
    "            return False\n",
    "        flag=False\n",
    "        memo=dict()\n",
    "        \n",
    "        \n",
    "        def dp(i,j,flag):\n",
    "            if flag==False and len(s[:i+1])==0 and len(t[:j+1])==1:\n",
    "                return True\n",
    "            if flag==False and len(s[:i+1])==1 and len(t[:j+1])==0:\n",
    "                return True\n",
    "            \n",
    "            if flag==True and i==-1 and j==-1:\n",
    "                return True\n",
    "            if flag==True and s[:i+1]==t[:j+1]:\n",
    "                return True\n",
    "            elif flag==True and (not s[:i+1]==t[:j+1]):\n",
    "                return False\n",
    "            \n",
    "            if (i,j) in memo.keys():\n",
    "                return memo[(i,j)]\n",
    "            \n",
    "            if s[i]==t[j]:\n",
    "                if (i,j) not in memo.keys():\n",
    "                    memo[(i,j)]=dp(i-1,j-1,flag)\n",
    "                return memo[(i,j)]\n",
    "            else:\n",
    "                flag=True\n",
    "                sign=dp(i,j-1,flag) or dp(i-1,j,flag) or dp(i-1,j-1,flag)\n",
    "                memo[(i,j)]=sign\n",
    "                return sign\n",
    "        return dp(len1-1,len2-1,flag)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneEditDistance(self, s: str, t: str) -> bool:\n",
    "\n",
    "        # s[0:i] 与 t[0:j] 的编辑距离是否为1\n",
    "        def dp(i,j,dis):\n",
    "            if dis < 0:\n",
    "                return False\n",
    "            if i == -1 or j == -1:\n",
    "                return abs(i-j) == dis\n",
    "            if s[i] == t[j]:\n",
    "                return dp(i-1,j-1,dis)\n",
    "            else:\n",
    "                return dp(i-1,j,dis-1) or dp(i,j-1,dis-1) or dp(i-1,j-1,dis-1)\n",
    "        m,n = len(s),len(t)\n",
    "        ans = dp(m-1,n-1,1)\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
